/* 
    快速排序
    1.选定Pivot中心轴
    2.将大于Pivot的数字放在Pivot的右边
    3.将小于Pivot的数字放在Pivot的左边
    4.分别对左右子序列重复上面3步操作
*/

const partition = (arr, low, high) => {
	let pivot = arr[low]
	while (low < high) {
		/* 只能先找比pivot小的，避免把基准值多次赋值给arr[high] */

		// 找到比基准值小的
		while (low < high && arr[high] > pivot) {
			--high
		}
		arr[low] = arr[high]

		// 找到比基准值大的
		while (low < high && arr[low] <= pivot) {
			++low
		}
		arr[high] = arr[low]
	}
	// low === high
	arr[low] = pivot
	return low
}
const quickSort = (arr, low, high) => {
	if (low < high) {
		// 中心轴，默认最左边的一个
		const pivot = partition(arr, low, high)
		quickSort(arr, low, pivot - 1)
		quickSort(arr, pivot + 1, high)
	}
	return arr
}

const arr = quickSort([1, 5, 2, 7, 0, 10], 0, 5)
console.log('quickSort :>>', arr)
